package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
// Leetcode 31. 给定一组数字，任意组合，求比给定组合M大的最小值
public class Ex31 {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
      	int len = nums.length;
        //越底层的交换越小
        int i = len - 1, j = len - 2;
        for (; i > 0; i--) {
/*             for (j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    swap(i, j, nums);
                    return;
                }
            } */
            //优化：若对于上一个i，不存在nums[i - 1] < nums[i], 就说明在(i - 1..)到后面都是单调递减的
            if (nums[i] > nums[i - 1]) {
                break;
            }
        }
        if (i == 0) {
            for (i = 0; i < len / 2; i++) {
                swap(i, len - i - 1, nums);
            }
        } else {
            for (j = len - 1; j >= i; j--) {
                if (nums[j] > nums[i - 1]) {
                    swap(i - 1, j, nums);
                    reverse(i, nums);
                    return;
                }
            }
        }
    }

    public void swap(int i , int j, int[] ss) {
        int t = ss[i];
        ss[i] = ss[j];
        ss[j] = t;
    }

    public void reverse(int start, int[] nums) {
        int lo = start, hi = nums.length - 1;
        for (; lo < (lo + hi + 1) / 2; lo++) {
            swap(lo, hi--, nums);
        }
    }

    @Test
    public void test() {
        int[] nums = new int[]{1,2,3,8,5,7,6,4};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
